home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 6666 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.1 KB
  1. Path: mail2news.demon.co.uk!genesis.demon.co.uk
  2. From: Lawrence Kirby <fred@genesis.demon.co.uk>
  3. Newsgroups: comp.lang.c,comp.sys.amiga.programmer
  4. Subject: Re: MY SORT DOESN'T QUICK!
  5. Date: Sat, 30 Mar 96 20:33:04 GMT
  6. Organization: none
  7. Message-ID: <828217984snz@genesis.demon.co.uk>
  8. References: <2082.6659T1310T2974@xs4all.nl>
  9. Reply-To: fred@genesis.demon.co.uk
  10. X-NNTP-Posting-Host: genesis.demon.co.uk
  11. X-Newsreader: Demon Internet Simple News v1.27
  12. X-Mail2News-Path: genesis.demon.co.uk
  13.  
  14. In article <2082.6659T1310T2974@xs4all.nl>
  15.            muaddib@xs4all.nl "Thomas van Gulick" writes:
  16.  
  17. >Help! My Sort doesn't Quick (ie, it doesn't work for all inputs!)
  18. >Something goes wrong when the array is being split into two parts,
  19. >but how to solve it, beats me. (ULONG = unsigned long btw)
  20. >
  21. >The array where this function fails:
  22. >
  23. >{ 110, 1664, 96781, 1, 5, 10, 1120, 10, 130, 10 }
  24.  
  25. You have a small set of data here that shows the problem. Run therough the
  26. code step by step with that data (probably best by hand although you
  27. might use a debugger) untill you see something that goes wrong. That should
  28. give you a clue as to what the problem is.
  29.  
  30. The question is though why are you doing this? Is it a assignment or are
  31. you just interested in getting to know some sort algorithms? I assume that
  32. yoy don't simply need a sort for an application since you could use qsort()
  33. for that or get much better code off the net.
  34.  
  35. >VOID
  36. >QuickSort
  37. >(
  38. >    ULONG   Array[],
  39. >    ULONG   lo0,
  40. >    ULONG   hi0
  41. >)
  42. >{
  43. >    ULONG lo = lo0;
  44. >    ULONG hi = hi0;
  45. >
  46. >    if( lo < hi )
  47. >    {
  48. >        ULONG mid;
  49. >
  50. >        mid = Array[ ( lo + hi ) / 2 ];
  51. >
  52. >        while( lo < hi )
  53. >        {
  54. >            while( Array[ lo ] < mid )
  55. >                lo ++;
  56. >
  57. >            while( Array[ hi ] > mid )
  58. >                hi --;
  59. >
  60. >            if( lo < hi )
  61. >            {
  62. >                ULONG swap;
  63. >
  64. >                swap        = Array[ lo ];
  65. >                Array[ lo ] = Array[ hi ];
  66. >                Array[ hi ] = swap;
  67. >
  68. >                lo ++;
  69. >                hi --;
  70. >            }
  71. >        }
  72. >        QuickSort( Array, lo0, hi );
  73. >        QuickSort( Array, lo == hi ? lo + 1 : lo, hi0 );
  74. >    }
  75. >}
  76.  
  77. A proper partitioning algorithm will arrange the elements so that they
  78. satisfy 3 properties:
  79.  
  80. 1. The 'pivot' is in its final position for the entire sort i.e. never
  81.    needs to be moved again.
  82.  
  83. 2. All elements positioned lower than the pivot compare less than or equal to
  84.    it.
  85.  
  86. 3. All elements positioned higher than the pivot compare greater than or
  87.    equal to it.
  88.  
  89. The code above doesn't appear to position the pivot element properly (what
  90. you are storing in mid), it just seems to try to create 2 ranges, which is
  91. not a correct approach for partitioning.
  92.  
  93. >I need an answer or solution as soon as possible! It's of a live saving matter!
  94. >(Well sort of:)
  95.  
  96. What do you need it for?
  97.  
  98. >Oh, and don't tell me it is built into my compiler.
  99.  
  100. While it doesn't necessarily implement quicksort, qsort() is part of the
  101. standard library.
  102.  
  103. -- 
  104. -----------------------------------------
  105. Lawrence Kirby | fred@genesis.demon.co.uk
  106. Wilts, England | 70734.126@compuserve.com
  107. -----------------------------------------
  108.